\documentclass[a4paper, 10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[italian]{babel}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{epstopdf}
\usepackage{braket}
\usepackage{mathtools}
\usepackage{amsthm}
\usepackage{tikz}
\usepackage{amsfonts} %reali, naturali
\usepackage{algorithm, algorithmic} % algoritmi
\usepackage{array}

\graphicspath{{Immagini/}}

\title{Elaborato Immagini: Halftoning}
\author{Jacopo Mocci VR092663 \\ Andrea Bertolaso VR091629}
\date{}


\begin{document}
\maketitle
%\newpage

\section{Introduzione}
L'\emph{halftoning} è una tecnica di elaborazione dell'immagine che permette, partendo da immagine a toni continui, di ottenere immagini con un numero ridotto di colori. Questo procedimento risulta utile nel momento in cui l'immagine deve essere rappresentata tramite dispositivi con risorse limitate, ad esempio una stampante (quattro colori) o uno schermo con intensità di colore ridotta.

L'halftoning simula la continuità dei toni tramite punti che variano in dimensione, distanza o forma. Il risultato è un'illusione ottica che l'occhio percepisce come sfumature continue.

In questa sede esamineremo brevemente come viene effettuato l'halftoning per la stampa per poi passare ad analizzare l'halftoning digitale vedendone in dettaglio alcuni algoritmi.

\section{Halftoning per la stampa}

\subsection{Imamgini in scala di grigi}
Prendiamo come esempio la Figura \ref{fig:gradient_half}. Nell'immagine in alto è rappresentato un gradiente a infinite sfumature intermedie di grigio. Così com'è non può essere riprodotta da una stampante in quanto questa è in grado di creare solamente aree di inchiostro pieno.

L'immagine viene pertanto convertita in una immagine \emph{binaria}, composta da una griglia regolare di punti di dimensioni differenti. 

\begin{figure}[h]
\centering
\includegraphics[scale=0.6]{immagini/halftone_gradient.jpg}
\caption{Halftone di un gradiente}
\label{fig:gradient_half}
\end{figure}

La dimensione dei punti è proporzionale al colore da rappresentare, più esso è scuro e più il punto sarà grande, più è chiaro e più il punto risulterà piccolo.

La risoluzione di una immagine halftone, viene misurata in linee per pollice (\emph{LPI}), dove per linee si intendono le linee di punti. Il numero di linee dipende dal tipo di carta usata per la stampa. La carta da giornale ad esempio è molto porosa e l'inchiostro tende a dilatarsi. Se le linee fossero troppo fitte i punti si unirebbero e l'immagine risulterebbe difficilmente comprensibile, pertanto il numero di LPI dei giornali è relativamente basso rispetto a quello impiegato in riviste o libri d'arte.

\begin{figure}[h]
\centering
\includegraphics[scale=0.6]{immagini/halftone_lpi.jpg}
\caption{Esempi per valori diversi di LPI}
\end{figure}


\subsection{Immagini a colori}

Quando viene stampata un immagine a colori è necessario ottenere l'halftone per ciascun colore sottrattivo primario utilizzato per la stampa (di solito ciano, magenta, giallo e nero). Il passo successivo è sovrapporli.

Quando i quattro differenti livelli vengono sovrapposti è necessario che siano sfasati ciascuno di un certo angolo.  (si veda Figura \ref{img:halftone_blend} per alcuni esempi di sovrapposizione).

\begin{figure}[h]
\centering
\includegraphics[scale=0.6]{immagini/halftone_blend.png}
\caption{Alcuni esempi su come ottenere diversi colori a partire dalla sovrapposizione di quelli primari per la stampa (CMYK)}
\label{img:halftone_blend}
\end{figure}

Quanto detto per le immagini in bianco e nero vale anche per quelle a colori. La risoluzione si misura sempre in LPI parallelamente all'angolo di sfasatura di un determinato livello, e le immagini halftone per ciascun colore sono sempre immagini binarie contenenti griglie ordinate di punti di diverse dimensioni.


\subsection{Halftone sovrapposti}
\begin{figure}
\centering
\includegraphics[scale=0.6]{immagini/halftone_angles.png}
\caption{1.a) Immagine in cui è visibile un pattern dovuto alla regolarità della griglia, l'effetto viene ridotto in 1.b.  2.a) Pattern di moiré con sfasatura di 5 gradi. 2.b) Sfasatura di 10 gradi}
\label{img:halftone_angles}
\end{figure}

Spesso è necessario sovrapporre diverse immagini halftone (accede ad esempio nelle immagini a colori).

Poiché le immagini halftone sono composte da griglie ordinate di punti sono visibili dei pattern sull'immagine stampata finale.

Già in una singola immagine halftone in bianco e nero questi pattern sono molto visibili. Per minimizzarne la visibilità è sufficiente ruotare la griglia di 45 gradi (Figura \ref{img:halftone_angles}.1).

Quando due o più immagini halftone vengono sovrapposte si creano dei pattern fastidiosi alla vista noti come pattern di \emph{moiré}. Questi pattern sono tanto più sgradevoli quanto minore è la sfasatura tra gli angoli delle immagini (si veda Figura \ref{img:halftone_angles}.2).

Quando vengono stampate immagini a colori bisogna considerare quattro angoli differenti compresi tra 0 e 90 gradi (poiché ogni 90 gradi le grigli si ripetono). In base a diverse considerazioni gli angoli migliori e più usati sono i seguenti (si veda Figura \ref{img:halftone_colours}):
\begin{itemize}
\item il giallo, che è il colore meno visibile, viene posto con un inclinazione di 0 gradi, ovvero l'inclinazione più visibile;
\item il nero, che è invece il colore più visibile vine posto ad una inclinazione di 45 gradi;
\item ciano e magenta stanno tra i due precedenti con inclinazione rispettivamente di 15 e 75 gradi.
\end{itemize}

\begin{figure}[h]
\centering
\includegraphics[scale=0.6]{immagini/halftone_colours.png}
\caption{Inclinazioni diverse per i diversi colori}
\label{img:halftone_colours}
\end{figure}

\section{Halftoning digitale}

\subsection{Introduzione al Dithering}

Un problema importante della computer grafica è la rappresentazione su dispositivi di visualizzazione che fanno uso di una matrice di punti fissa (schermi CRT e LCD, videoproiettori...) in quanto l'immagine soffre di restrizioni nella risoluzione di \emph{intensità} (numero di colori disponibili), di \emph{spazialità} (numero di pixel disponibili) e di \emph{temporaneità} (frequenza di aggiornamento dell'immagine).

L'argomento affrontato è la limitazione della risoluzione di intensità che trova le sue ragioni nella \emph{quantizzazione} di un segnale anche già discretizzato. Prendiamo come esempio la figura \ref{fig:quantization}: un'immagine ad 8 bit di risoluzione di intensità (profondità) equivalenti a 256 livelli possibili ed un dispositivo di visualizzazione a 1 bit di profondità - 2 livelli possibili: l'algoritmo di quantizzazione più semplice prevede che l'intensità di ogni punto dovrà essere divisa per 256 (livelli originali) e moltiplicato per 2 (livelli dispositivo), la parte decimale del risultato confrontata con un valore soglia (da 0 a 1) ed in base a questo l'arrotondamento all'intero superiore od inferiore. \emph{L'arrotondamento è la vera azione distruttiva non reversibile dell'informazione} di intensità: più la distanza in bit fra immagine e dispositivo è alta e più informazione viene persa.

Le immagini più sensibili alla quantizzazione sono quelle che contengono gradienti morbidi: il risultato è spesso una caratteristica composizione di bande di colore omogeneo (fenomeno conosciuto come \emph{banding}) che oltre ad indicare un'evidente perdita di informazione è anche percettualmente di qualità scadente.

\begin{figure}[h]
\centering
\subfigure{\includegraphics[width=2.3in]{Originale_Colori}}
\subfigure{\includegraphics[width=2.3in]{Dither_Colori_Soglia_lv05}}
\caption{Effetto della quantizzazione (8bit $\rightarrow$ 1bit) su un'immagine a colori}
\label{fig:quantization}
\end{figure}

Il \emph{dithering} si offre quindi come possibile soluzione operando direttamente sulla quantizzazione dei livelli di colore variandone la soglia (a seconda dell'algoritmo) con l'assunzione - analoga a quella dell'halftoning di stampa - che l'occhio umano percepisce la media del colore di punti adiacenti dopo una certa distanza di osservazione. Bisogna notare che il \emph{dithering} è una tecnica valida per la quantizzazione di un segnale discreto di qualsiasi natura di tipo multimediale: basti pensare che è stato scoperto nella strumentazione di bordo degli aerei nella seconda guerra mondiale dove le imprecisioni introdotte dalla meccanica durante il volo rendevano il segnale migliore di quello ottenuto dalle sperimentazioni a terra (e da qui il termine \emph{dithering} - traduzione di \emph{smottamento}).

Il \emph{dithering} è quasi sempre l'ultimo stadio del processo complessivo di elaborazione delle immagini proprio perché fa da ponte fra l'immagine digitale e ciò che viene visualizzato: questo implica che tutte le operazioni di rimozione rumore, scalatura, miglioramento etc... devono essere fatte \emph{a priori}; tuttavia si può pretendere che il risultato del dithering possa a sua volta essere processato per ottenere effetti artistici.
   
\subsection{Algoritmi di Dithering}

Come accennato nell'introduzione gli algoritmi di \emph{dithering} operano sulla quantizzazione del segnale discreto. Una proprietà comune a tutti gli algoritmi mostrati è l'indipendenza fra canali di colore: per immagini a più canali è sufficiente applicare l'algoritmo per ogni canale.

Ogni algoritmo mostrato è stato implementato in MatLab (figura \ref{fig:matlab}): l'immagine di ingresso viene letta dal comando \texttt{imread()} ed ha una risoluzione di intensità di 8 bit (corrispondente a 256 livelli di intensità) per ogni canale di colore (bianco/nero oppure rosso, verde e blu) e viene trasformata in un'immagine risultante che \emph{simula} n bit per canale (con n < 8). L'intensità calcolata da ogni algoritmo viene infatti moltiplicata per il rapporto dei livelli originali sui livelli risultanti - questo esclusivamente per facilità di rappresentazione tramite il comando \texttt{imshow()} (che non consente la visualizzazione di immagini con un numero arbitrario di bit di profondità).

\begin{figure}[H]
\centering
\includegraphics[width=5in]{Matlab_GUI}
\caption{Programma MatLab per l'applicazione degli algoritmi di dithering}
\label{fig:matlab}
\end{figure}

\subsubsection{Sogliatura}
L'algoritmo più semplice è quello della sogliatura ed è stato implementato per fornire una buona visione del problema dato. (Algoritmo \ref{alg:thresholding}, figure \ref{fig:sogliatura} e \ref{fig:sogliaturacolori})

\begin{algorithm}[H]
\caption{\texttt{Thresholding}($threshold$)}
\begin{algorithmic}
\ENSURE $0 < threshold < 1$
\FORALL {$y$ from up to down} 
	\FORALL {$x$ from left to right}
		\STATE $old \leftarrow image(x, y)$
		\STATE $new \leftarrow old * deviceLevels / originalLevels$
		\IF {$new$'s decimal part $\leq threshold$}
			\STATE $result(x, y) \leftarrow floor(new)$
		\ELSE
			\STATE $result(x, y) \leftarrow ceil(new)$
		\ENDIF
	\ENDFOR
\ENDFOR
\end{algorithmic}
\label{alg:thresholding}
\end{algorithm}

\begin{figure}[H]
\centering
\subfigure{\includegraphics[width=2.3in]{Dither_Soglia_lv02}}
\subfigure{\includegraphics[width=2.3in]{Dither_Soglia_lv05}}
\subfigure{\includegraphics[width=2.3in]{Dither_Soglia_lv08}}
\caption{Sogliatura a livello crescente di soglia}
\label{fig:sogliatura}
\end{figure}

\begin{figure}[H]
\centering
\subfigure{\includegraphics[width=2.3in]{Dither_Colori_Soglia_lv02}}
\subfigure{\includegraphics[width=2.3in]{Dither_Colori_Soglia_lv05}}
\subfigure{\includegraphics[width=2.3in]{Dither_Colori_Soglia_lv08}}
\caption{Sogliatura a livello crescente di soglia}
\label{fig:sogliaturacolori}
\end{figure}

\subsubsection{Rumore}
Questo algoritmo ricrea la situazione descritta nell'introduzione riguardo la strumentazione di bordo degli aeroplani in quanto aggiunge un'incertezza alla soglia di quantizzazione. (Algoritmo \ref{alg:noise}, figure \ref{fig:rumore} e \ref{fig:rumorecolori})

\begin{algorithm}[H]
\caption{\texttt{Random Noise}($noiseRatio$)}
\begin{algorithmic}
\ENSURE $0 < noiseRatio < 1$
\FORALL {$y$ from up to down} 
	\FORALL {$x$ from left to right}
		\STATE $old \leftarrow image(x, y)$
		\STATE $new \leftarrow round(old * deviceLevels / originalLevels + rand() * noiseRatio)$
		\STATE $result(x, y) \leftarrow new$
	\ENDFOR
\ENDFOR
\end{algorithmic}
\label{alg:noise}
\end{algorithm}

\begin{figure}[H]
\centering
\subfigure{\includegraphics[width=2.3in]{Dither_Rumore_lv02}}
\subfigure{\includegraphics[width=2.3in]{Dither_Rumore_lv05}}
\subfigure{\includegraphics[width=2.3in]{Dither_Rumore_lv08}}
\caption{Algoritmo del rumore a livelli crescenti di rumore}
\label{fig:rumore}
\end{figure}

\begin{figure}[H]
\centering
\subfigure{\includegraphics[width=2.3in]{Dither_Colori_Rumore_lv02}}
\subfigure{\includegraphics[width=2.3in]{Dither_Colori_Rumore_lv05}}
\subfigure{\includegraphics[width=2.3in]{Dither_Colori_Rumore_lv08}}
\caption{Algoritmo del rumore a livelli crescenti di rumore su un'immagine a colori}
\label{fig:rumorecolori}
\end{figure}

\subsubsection{Rumore ordinato}
Anche definito come algoritmo pseudo rumore; viene creata una matrice $N \times N$ tale che 1) contenga tutti i valori da $1$ a $N^2$ e 2) la somma degli elementi di righe e colonne è costante (in MatLab il comando per la creazione di tale matrice è \texttt{magic()}), e la soglia di quantizzazione per i punti dell'immagine viene scelta ciclando questa matrice. (Algoritmo \ref{fig:ordinatocolori}, figure \ref{fig:ordinato} e \ref{fig:ordinatocolori})
		
\begin{algorithm}[H]
\caption{\texttt{Ordered Noise}($N$)}
\begin{algorithmic}
\ENSURE $N \in \mathbb{N}^+$
\STATE $thresholdMatrix \leftarrow magic(N)$
\FORALL {$y$ from up to down} 
	\FORALL {$x$ from left to right}
		\STATE $old \leftarrow image(x, y)$
		\STATE $i \leftarrow x \mod{N}$
		\STATE $j \leftarrow y \mod{N}$
		\STATE $new \leftarrow old * deviceLevels / originalLevels$
		\IF {$new$'s decimal part $\leq thresholdMatrix(i, j)$}
			\STATE $result(x, y) \leftarrow floor(new)$
		\ELSE
			\STATE $result(x, y) \leftarrow ceil(new)$
		\ENDIF
	\ENDFOR
\ENDFOR
\end{algorithmic}
\label{alg:ordered}
\end{algorithm}

\begin{figure}[H]
\centering
\subfigure{\includegraphics[width=2.3in]{Dither_Ordinato_2}}
\subfigure{\includegraphics[width=2.3in]{Dither_Ordinato_3}}
\subfigure{\includegraphics[width=2.3in]{Dither_Ordinato_4}}
\caption{Algoritmo ordinato a dimensione matrice crescente}
\label{fig:ordinato}
\end{figure}

\begin{figure}[H]
\centering
\subfigure{\includegraphics[width=2.3in]{Dither_Colori_Ordinato_2}}
\subfigure{\includegraphics[width=2.3in]{Dither_Colori_Ordinato_3}}
\subfigure{\includegraphics[width=2.3in]{Dither_Colori_Ordinato_4}}
\caption{Algoritmo ordinato a dimensione matrice crescente su un'immagine a colori}
\label{fig:ordinatocolori}
\end{figure}

\subsubsection{Floyd-Steinberg}
Mentre dall'intensità quantizzata di un punto è impossibile risalire all'intensità iniziale, è comunque possibile distribuire l'errore di quella quantizzazione ai punti vicini in modo che ne abbiano 'memoria' per consentire un gradiente meno brusco. Uno dei primi algoritmi ad usare questo concetto è quello sviluppato da Floyd-Steinberg, diviso in 2 parti principali: ogni punto distribuisce il suo errore di quantizzazione a quelli adiacenti ancora da quantizzare, ed ogni punto somma alla sua intensità gli errori presenti nella sua posizione. (Algoritmo \ref{alg:fs}, figure \ref{fig:floyd} e \ref{fig:floydcolori})
		
\begin{algorithm}[H]
\caption{\texttt{Floyd-Steinberg}}
\begin{algorithmic}
\FORALL {$y$ from up to down} 
	\FORALL {$x$ from left to right}
		\STATE $old \leftarrow image(x, y) + result(x, y)$
		\STATE $new \leftarrow round(old * deviceLevels / originalLevels)$
		\STATE $qError \leftarrow old - new$
		\STATE $result(x, y) \leftarrow new$
		\STATE $result(x+1, y) \leftarrow result(x+1, y) * qError * 7/16$
		\STATE $result(x-1, y+1) \leftarrow result(x-1, y+1) * qError * 3/16$
		\STATE $result(x, y+1) \leftarrow result(x, y+1) * qError * 5/16$
		\STATE $result(x+1, y) \leftarrow result(x+1, y) * qError * 1/16$
	\ENDFOR
\ENDFOR
\end{algorithmic}
\label{alg:fs}
\end{algorithm}

\begin{figure}[H]
\centering
\includegraphics[width=2.5in]{Dither_Floyd-Steinberg}
\caption{Algoritmo di Floyd-Steinberg}
\label{fig:floyd}
\end{figure}

\begin{figure}[H]
\centering
\includegraphics[width=2.5in]{Dither_Colori_Floyd-Steinberg}
\caption{Algoritmo di Floyd-Steinberg su un'immagine a colori}
\label{fig:floydcolori}
\end{figure}

\subsubsection{Halftoning}
Fra tutti gli algoritmi questo è l'eccezione che esce dal paradigma della soglia di quantizzazione - come suggerito dal nome, l'analogia con l'halftoning per la stampa è molto forte. Viene scelta un vettore di $N^2+1$ matrici, a valori binari, di dimensione $N \times N$, che rappresenta i possibili livelli crescenti di intensità - che devono ovviamente essere più di quelli resi disponibili dal dispositivo (il modo in cui queste matrici vengono riempite deve essere 'piacevole'); l'immagine originale viene divisa in cluster di dimensione $N \times N$ e ne viene calcolata l'intensità (spesso viene presa semplicemente l'intensità del primo punto); ogni cluster viene quantizzato secondo gli $N^2+1$ livelli e viene sostituito dalla matrice corrispondente. (Algoritmo \ref{alg:halftoning}, figure \ref{fig:ditherhf} e \ref{fig:ditherhfcolori})

\begin{algorithm}[H]
\caption{\texttt{Halftoning}($N$)}
\begin{algorithmic}
\STATE $halftoneLevels \leftarrow N^2+1$
\FOR {$i=0$ \TO $halftoneLevels$}
	\STATE $cluster \leftarrow N*N$ binary matrix of intensity $i$ out of $halftoneLevels$
	\STATE $halftoneVector \leftarrow cluster$
\ENDFOR
\FORALL {$y$ from up to down} 
	\FORALL {$x$ from left to right}
		\STATE $old \leftarrow image(x*N, y*N)$
		\STATE $new \leftarrow round(old * deviceLevels / originalLevels)$
		\STATE $result(x*N, y*N) \leftarrow halftoneVector(new)$
	\ENDFOR
\ENDFOR
\end{algorithmic}
\label{alg:halftoning}
\end{algorithm}

\begin{figure}[H]
\centering
\includegraphics[width=2.5in]{Dither_Halftone_3}
\caption{Algoritmo halftoning con cluster intensità $3 \times 3$}
\label{fig:ditherhf}
\end{figure}

\begin{figure}[H]
\centering
\includegraphics[width=2.5in]{Dither_Colori_Halftone_3}
\caption{Algoritmo halftoning con cluster intensità $3 \times 3$ su un'immagine a colori}
\label{fig:ditherhfcolori}
\end{figure}

\end{document}